package 经典例题;

//给定有向图，设计一个算法，找出两个节点之间是否存在一条路径。
public class 节点间通路 {

    // 调用自身
//    public boolean findWhetherExistsPath(int n, int[][] graph, int start, int target) {
//        if (start==target)
//            return true;
//        for (int[] ints : graph) {
//            if (ints[1]==target)
//                return findWhetherExistsPath(n,graph,start,ints[0]);
//        }
//        return false;
//    }
    //dfs
    boolean[] booleans=null;
    public boolean findWhetherExistsPath(int n, int[][] graph, int start, int target) {
        booleans = new boolean[graph.length];
        return bfs(graph,start,target);
    }

    private boolean bfs(int[][] graph, int start, int target) {
        for (int i = 0; i < graph.length; i++) {
           if (!booleans[i]) {
               if (graph[i][0] == start && graph[i][1] == target)
                   return true;
               booleans[i] = true;
               if (graph[i][1] == target && bfs(graph, start, graph[i][0]))
                   return true;
               booleans[i] = false;
           }
        }
        return false;
    }
}
